package BinaryTree.BinarySearchTree;

import java.util.LinkedList;

/**
 * 搜索二叉树转双向链表
 *
 * @author Liaorun
 */
public class BSTtoDoubleLinkedList {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static Node convert1(Node head) {
        LinkedList<Node> queue = new LinkedList<>();
        inOrderToQueue(head, queue);

        if (queue.isEmpty()) {
            return head;
        }

        head = queue.poll();
        Node pre = head;
        pre.left = null;
        Node cur = null;

        while (!queue.isEmpty()) {
            cur = queue.poll();
            pre.right = cur;
            cur.left = pre;
            pre = cur;
        }
        pre.right = null;

        return head;
    }

    private static void inOrderToQueue(Node head, LinkedList<Node> queue) {
        if (head == null) {
            return;
        }
        inOrderToQueue(head.left, queue);
        queue.offer(head);
        inOrderToQueue(head.right, queue);
    }

    public static Node convert2(Node head) {
        if (head == null) {
            return null;
        }
        return process(head).start;
    }

    /**
     * 将一颗树变成双向链表
     *
     * @param x
     * @return
     */
    private static ReturnType process(Node x) {
        // base case
        if (x == null) {
            return new ReturnType(null, null);
        }

        // 左子树变成双向链表
        ReturnType leftHeadEnd = process(x.left);
        // 右子树变成双向链表
        ReturnType rightHeadEnd = process(x.right);

        if (leftHeadEnd.end != null) {
            // 左子树变成双向链表之后 的尾巴节点 的右指针 = 当前节点
            leftHeadEnd.end.right = x;
        }

        // 当前节点的左指针 = 左子树变成双向链表的尾巴节点
        x.left = leftHeadEnd.end;
        // 当前节点的右指针 = 右子树变成双向链表的开始节点
        x.right = rightHeadEnd.start;

        if (rightHeadEnd.start != null) {
            // 右子树变成双向链表之后 的开始节点 的左指针 = 当前节点
            rightHeadEnd.start.left = x;
        }


        return new ReturnType(leftHeadEnd.start != null ? leftHeadEnd.start : x,
                // 双端链表的尾巴 == 右子树返回了尾巴节点 ？  右子树返回的尾巴节点 ： 当前节点
                rightHeadEnd.end != null ? rightHeadEnd.end : x);
    }

    /**
     * 搜索二叉树转化成双向链表之后，头和尾巴返回
     */
    public static class ReturnType {
        public Node start;
        public Node end;

        public ReturnType(Node start, Node end) {
            this.start = start;
            this.end = end;
        }
    }

    public static void printBSTinOrder(Node head) {
        if (head != null) {
            inOrderPrint(head);
        }

        System.out.println();
    }

    private static void inOrderPrint(Node head) {

    }
}
